package DataStructure.arrayAndList.doublePoint;

import Top100.DoublePoint;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author liujun
 * @version 1.0
 * @date 2020/7/20
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 2数之和
 * 给定一个数 target，在一维数组中，找出某 2 个数相加得 target。
 * 返回所有的 2 数之和在数组中原位置的组合
 */

public class Find2ValueInArray_GetAllPosition implements FindValueinArray, DoublePoint {

    @Override
    public boolean exist(int[] array, int target) {
        return false;
    }

    @Override
    public List<int[]> getValues(int[] array, int target) {
        return null;
    }

    @Override
    public List<int[]> getPositions(int[] array, int target) {

        if (!check(array)) {
            return null;
        }
        Map<Integer, List> value_positionList_map = new TreeMap<>();

        List<int[]> statistic_list = new LinkedList();
        for (int i = 0; i < array.length; i++) {
            if (value_positionList_map.containsKey(array[i])) {
                List list = value_positionList_map.get(array[i]);
                list.add(i);
            } else {
                List list = new LinkedList();
                list.add(i);
                value_positionList_map.put(array[i], list);
            }
        }
        for (Integer value : value_positionList_map.keySet()) {
            List list = value_positionList_map.get(value);
            if (list == null) {
                continue;
            }

            int want = target - value;
            if (!value_positionList_map.containsKey(want) || value_positionList_map.get(want) == null) {
                continue;
            }
            List list1 = value_positionList_map.get(want);

            for (int i = 0; i < list.size(); i++) {
                for (int j = 0; j < list1.size(); j++) {
                    int[] r = (int) list1.get(j) > (int) list.get(i) ?
                            new int[]{(int) list.get(i), (int) list1.get(j)} :
                            new int[]{(int) list1.get(j), (int) list.get(i)};
                    statistic_list.add(r);
                }
            }
            value_positionList_map.put(value, null);
            value_positionList_map.put(want, null);
        }
        return statistic_list;
    }
}
